package q132_minCut;

import java.util.Arrays;

public class Solution {
    /*
    此题的前部分可以直接参考回文串分割131题
    首先利用一个二维数组 g
    对于i - j之间的字符串 g[i][j] = true代表是回文
    其模版不再赘述

    而对于最小分割方法 则直接使用动态规划 首先将f数组初始化为max value
    对于g[0][i]为true的 代表整段字符串都是回文 直接将f置0
    而如果不为true 则需要考虑0 - i之间的所有区间 是否有g[j + 1][i]是回文
    如果是 则代表f[i]可以由f[j] + 1推算而来
     */
    public int minCut(String s) {
        int len = s.length();
        boolean[][] g = new boolean[len][len];
        for (boolean[] row : g) {
            Arrays.fill(row, true);
        }

        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1; j < len; j++) {
                g[i][j] = s.charAt(i) == s.charAt(j) && g[i + 1][j - 1];
            }
        }

        int[] f = new int[len];
        Arrays.fill(f, Integer.MAX_VALUE);
        for (int i = 0; i < f.length; i++) {
            if (g[0][i]) {
                f[i] = 0;
            } else {
                for (int j = 0; j < i; j++) {
                    if (g[j + 1][i]) f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
        return f[len - 1];
    }
}
